package arithmetic.LeetCode.Move_Zeroes_and_Sort;

/**
 * @author zhangyanqi
 * @since 1.0 2017/10/12
 */
public class Solution {

    public void moveZeroes(int[] nums) {
        sort(nums, 0, nums.length - 1);
    }

    public static void sort(int[] nums, int begin, int end) {
        int length = nums.length;
        int position = getPosition(nums, begin, end);
        if (position - 1 > 0 && begin < position - 1) {
            sort(nums, begin, position - 1);
        }
        if (position + 1 < length && position + 1 < end) {
            sort(nums, position + 1, end);
        }
    }

    public static int getPosition(int[] nums, int beginIndex, int endIndex) {
        int pivot = nums[endIndex];
        if (pivot == 0) {
            return endIndex;
        }
        int storeIndex = beginIndex;
        for (int i = beginIndex; i <= endIndex; i++) {
            if (storeIndex == endIndex) {
                return storeIndex;
            }
            int currentPoint = nums[i];
            int store = nums[storeIndex];
            if (store < pivot && store != 0) {
                storeIndex++;
                if (i < storeIndex) {
                    i = storeIndex - 1;
                }
            } else {
                if ((currentPoint <= pivot && currentPoint != 0) || i == endIndex) {
                    nums[storeIndex] = currentPoint;
                    nums[i] = store;
                    if (i == endIndex) {
                        return storeIndex;
                    }
                    storeIndex++;
                    if (i < storeIndex) {
                        i = storeIndex - 1;
                    }
                }
            }//end else
        }
        return storeIndex;
    }

    public static void main(String[] args) {
        int[] i = {1, 3, 12, 0, 0}; //[1,3,12,0,0]
        new Solution().moveZeroes(i);
        for (int m = 0; m < i.length; m++) {
            System.out.println(i[m]);
        }
    }
}
